package com.example.demo.LeetCode.list;

import java.util.PriorityQueue;

/**
 * 合并多个链表
 */
public class MergeLists {
    public static void main(String[] args) {

        ListNode[] nodes = {createListNode1(),createListNode2(),createListNode3()};
        ListNode res = merge(nodes);
        while (res != null){
            System.out.println(res.val);
            res = res.next;
        }

    }



    //堆
    public  static  ListNode merge(ListNode[] lists){
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        //优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length,(a,b) -> a.val - b.val);
        //将k个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()){
            //获取最小节点,接到结果链表
            ListNode node = pq.poll();
            p.next = node;
            if(node.next != null){
                pq.add(node.next);
            }
            //p指针不断前进
            p = p.next;
        }
        return dummy.next;
    }

    private static  ListNode createListNode1(){
        ListNode head1 = new ListNode(1);
        ListNode next1 = new ListNode(4);
        ListNode next2 = new ListNode(5);
        head1.next = next1;
        next1.next = next2;
        return head1;
    }

    private static  ListNode createListNode2(){
        ListNode head1 = new ListNode(1);
        ListNode next1 = new ListNode(3);
        ListNode next2 = new ListNode(4);

        head1.next = next1;
        next1.next = next2;

        return head1;
    }

    private static  ListNode createListNode3(){
        ListNode head1 = new ListNode(2);
        ListNode next1 = new ListNode(6);

        head1.next = next1;

        return head1;
    }

    private static  ListNode createListNode4(){
        ListNode head1 = new ListNode(2);
        ListNode next1 = new ListNode(4);
        ListNode next2 = new ListNode(6);
        ListNode next3 = new ListNode(8);
        head1.next = next1;
        next1.next = next2;
        next2.next = next3;
        return head1;
    }


}
